package leetcode_周赛._2023._09;

import java.util.Collections;
import java.util.List;

/**
 * 第 363 场周赛 <p>
 * AC_2
 *
 * @author yezh
 * @date 2023/9/18 9:37
 */
public class _17 {

    /**
     * 让所有学生保持开心的分组方法数 <p />
     * 算法：贪心 + 排序 <p />
     * 在选择人数固定的时候, 选择的方案也是唯一的 <br />
     * 排序后, 小的在前, 如果当前被选中, 则前一个元素肯定要被选中, <br />
     * 因为如果选了后面的数, 后面的数可能比当前的数大, 那么选中的人数就变成了要大于后面的数 <p />
     * 选了 k 个学生, 则 nums[i] < k 的学生都选, nums[i] > k 的学生都不选, 并且不能出现 nums[i] = k 的情况
     */
    public int countWays(List<Integer> nums) {
        Collections.sort(nums);
        int ans = nums.get(0) > 0 ? 1 : 0, n = nums.size();
        for (int i = 0; i < n - 1; i++) if (nums.get(i) < i + 1 && i + 1 < nums.get(i + 1)) ++ans;
        // 因为题目的条件 -- 0 <= nums[i] < nums.length, 所以全选满足条件
        return ans + 1;
    }

}
